package 力扣.队列.单调队列;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 滑动窗口的最大值239 {
    public static void main(String[] args)  {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
/*        Scanner bf = new Scanner(System.in);
        int len = bf.nextInt();
        int k = bf.nextInt();

        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            nums[i] = bf.nextInt();
        }*/
        int[] intsMax = maxSlidingWindow3(nums, k);
//        int[] intsMin = maxSlidingWindow2(nums, k);
//        System.out.println(Arrays.toString(intsMin));
        System.out.println(Arrays.toString(intsMax));
    }
    //单调递减队列
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            int te = nums[i];
            //入队
            while(!deque.isEmpty() && te > nums[deque.peekLast()]){//保证单调递减队列
                deque.pollLast();
            }
            deque.offerLast(i);

            if(i < k - 1){//保证窗口大小为k
                continue;
            }

            //出队：最大值不在这个窗口中
            if (deque.getFirst() == i - k){
                deque.pollFirst();
            }
            ans [i - k + 1] = nums[deque.getFirst()];
        }
        return ans;
    }
    //滑动窗口最小值：单调递增序列
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //入队
            while (!deque.isEmpty() && nums[deque.peekLast()] > nums[i]){//比较队尾元素
                deque.pollLast();
            }
            deque.offerLast(i);

            if (i < k - 1){
                continue;
            }

            //出队：如果最大值不在这个窗口中
            if (i - deque.getFirst() == k){
                deque.pollFirst();
            }
            ans [i - k + 1] = nums[deque.getFirst()];
        }
        return ans;
    }


    public static int[] maxSlidingWindow3(int[] nums, int k) {
        if(nums.length == 0){
            return new int[]{};
        }
        Deque<Integer> queue = new LinkedList<>();
        int[] ans = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
              while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
                  queue.pollLast();
              }
              queue.addLast(i);
              if (i < k - 1){
                  continue;
              }
              while (!queue.isEmpty() && queue.peekFirst() <= (i - k)){
                  queue.pollFirst();
              }
              ans[i - k + 1] = nums[queue.peekFirst()];
        }
        return ans;
    }
    //优先队列
    public static int[] maxSlidingWindow4(int[] nums, int k) {
        PriorityQueue<Integer[]> pq = new PriorityQueue<>(new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {// 0: 元素值 1：元素索引
                return o2[0] - o1[0];
            }
        });
        int[] ans = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            pq.offer(new Integer[]{nums[i],i});
            if (i < k - 1){
                continue;
            }
            while (pq.peek()[1] <= (i - k)){
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;

    }
}
